/**
 * @param {number[]} bills
 * @return {boolean}
 */
export var lemonadeChange = function (bills) {
  const wallet = { 5: 0, 10: 0, 20: 0 }
  const billCate = [10, 5]
  wrapperLabel: for (const bill of bills) {
    wallet[bill] += 1
    let residual = bill - 5 // 差多少钱要找
    for (const k of billCate) {
      let cnt = wallet[k]
      let [l, r] = [0, cnt]
      let n = 0 //记录要用多少张k元钱
      while (l <= r) {
        const mid = (r + l) >> 1
        if (mid * k === residual) {
          // 如果 mid 张k元钱可以找成功，则扣除钱包的钱后给进行下一轮客人找钱
          wallet[k] -= mid
          continue wrapperLabel
        }
        if (mid * k < residual) {
          n = mid
          l = mid + 1
        } else {
          r = mid - 1
        }
      }
      wallet[k] -= n
      residual -= n * k
    }
    if (residual > 0) {
      return false
    }
  }
  return true
}

/**
 * 方法二
 * @param {number[]} bills
 * @return {boolean}
 */
export var lemonadeChange2 = function (bills) {
  let five = 0,
    ten = 0
  for (const bill of bills) {
    if (bill === 5) {
      five += 1
    } else if (bill === 10) {
      if (five === 0) {
        return false
      }
      five -= 1
      ten += 1
    } else {
      if (five > 0 && ten > 0) {
        five -= 1
        ten -= 1
      } else if (five >= 3) {
        five -= 3
      } else {
        return false
      }
    }
  }
  return true
}
